package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC95 {
    public static void main(String[] args) {

    }

    public int numTrees(int n) {
        int[] ans = new int[n+1]; //长度为n的二叉树有多少种
        ans[0] = 1;
        ans[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {// 左子树的数量
                ans[i] = ans[j-1]*ans[i-j];
            }
        }
        return ans[n];

    }
}
